package engine;

import java.io.ObjectInputStream.GetField;
import java.util.ArrayList;

public class Cache extends MemoryHierarchy {

	private int S; // net cache size
	private int L; // #of lines/blocks in cache
	private int M; // #of sets
	private int type; // 0 DirectMap - 1 set associative - 2 fully associative
	public ArrayList<ArrayList<CacheEntry>> entries;
	private MemoryHierarchy nextLevel;
	private int HWritePolicy; // 0 write through - 1 write back
	private int MWritePolicy; // 0 write through with arround - 1 write through
	private int hits, accesses;// with allocate - 2 write back
	private int accessTime;

	public Cache(int _S, int _L, int _M, int _HWritePolicy, int _MWritePolicy,
			int _accessTime) {
		this.S = _S;
		this.L = _L;
		this.M = _M;
		this.HWritePolicy = _HWritePolicy;
		this.MWritePolicy = _MWritePolicy;
		accessTime = _accessTime;
		entries = new ArrayList<ArrayList<CacheEntry>>(S / L);
		if (M == 1) {
			type = 0;
		} else {
			if (M == (S / L)) {
				type = 2;
			} else {
				type = 1;
			}
		}
		for (int i = 0; i < S / (L * M); i++) {
			entries.add(new ArrayList<CacheEntry>());
			for (int j = 0; j < M; j++) {
				entries.get(i).add(new CacheEntry(L));
			}
		}

	}

	// convert
	public int ones(int num) {
		int result = 0;
		for (int i = 0; i < num; i++) {
			result = result << 1;
			result++;

		}
		return result;
	}

	static int log(int x, int base) {
		return (int) (Math.log(x) / Math.log(base));
	}

	public int[] decodeAddress(int address) {
		int decodedAddress[] = new int[3];
		decodedAddress[0] = address >> (log((S / (L * M)), 2) + log(L, 2));
		decodedAddress[1] = (address >> log(L, 2))
				& (ones(log(S / (L * M), 2)));
		decodedAddress[2] = address & (ones(log(L, 2)));
		// System.out.println(decodedAddress[0]);
		// System.out.println(decodedAddress[1]);
		// System.out.println(decodedAddress[2]);
		return decodedAddress;
	}

	public int encodeAddress(int oldtag, int address) {
		int decodedAddress[] = new int[3];
		decodedAddress[0] = address >> (log((S / (L * M)), 2) + log(L, 2));
		decodedAddress[1] = (address >> log(L, 2))
				& (ones(log(S / (L * M), 2)));
		decodedAddress[2] = address & (ones(log(L, 2)));
		int result = oldtag << (log((S / (L * M)), 2) + log(L, 2));
		result |= decodedAddress[1] << log(L, 2);
		result |= decodedAddress[2];
		return result;
	}

	public void setNextLevel(MemoryHierarchy next) {
		this.nextLevel = next;
	}

	public ArrayList<String> read(int address) {
		accesses++;
		latency += accessTime;
		int[] decoded = decodeAddress(address);
		int tag = decoded[0];
		int index = decoded[1];
		int offset = decoded[2];
		ArrayList<String> result = null;
		// incase Hit
		switch (type) {
		case 0: {
			result = entries.get(index).get(0).tag == tag
					&& entries.get(index).get(0).valid ? entries.get(index)
					.get(0).words : null;
		}
			break;
		case 1: {
			for (int i = 0; i < entries.get(index).size(); i++) {
				if (tag == entries.get(index).get(i).tag
						&& entries.get(index).get(i).valid) {
					result = entries.get(index).get(i).words;
				}
			}
		}
			break;
		case 2: {
			for (int i = 0; i < entries.get(0).size(); i++) {
				if (tag == entries.get(0).get(i).tag
						&& entries.get(0).get(i).valid) {
					result = entries.get(0).get(i).words;
				}
			}
		}
			break;

		}

		// incase of miss
		if (result == null) {

			// got to the next level
			result = ((MemoryHierarchy) nextLevel).read(address);
			latency += accessTime;
			// placement-replacement
			switch (type) {
			case 0: {// direct-map
				if (HWritePolicy == 1) {
					if (entries.get(index).get(0).dirty) {
						if (nextLevel instanceof Memory) {
							entries.get(index).get(0).dirty = false;
							entries.get(index).get(0).valid = true;
							;
							ArrayList<String> dirty_block = entries.get(index)
									.get(0).words;
							entries.get(index).get(0).words = result;
							((MemoryHierarchy) nextLevel).writeBlock(
									encodeAddress(
											entries.get(index).get(0).tag,
											address), dirty_block);
							entries.get(index).get(0).tag = tag;
							latency += accessTime;
						} else {
							entries.get(index).get(0).words = result;
							entries.get(index).get(0).dirty = false;
							entries.get(index).get(0).tag = tag;
							entries.get(index).get(0).valid = true;
							;
						}
					} else {
						entries.get(index).get(0).words = result;
						entries.get(index).get(0).dirty = false;
						entries.get(index).get(0).tag = tag;
						entries.get(index).get(0).valid = true;
						;
					}

				} else {
					entries.get(index).get(0).words = result;
					entries.get(index).get(0).tag = tag;
					entries.get(index).get(0).valid = true;
					;
				}
			}
				break;
			case 1: {// set associative
				int not_dirty = -1;
				int found_empty = -1;
				for (int i = 0; i < entries.get(index).size(); i++) {
					if (entries.get(index).get(i).words.size() == 0) {
						found_empty = i;
					} else {
						if (not_dirty == -1)
							not_dirty = entries.get(index).get(i).dirty ? -1
									: i;
					}
				}
				if (found_empty != -1) {
					entries.get(index).get(found_empty).words = result;
					entries.get(index).get(found_empty).dirty = false;
					entries.get(index).get(found_empty).valid = true;
					entries.get(index).get(found_empty).tag = tag;
				} else {
					if (HWritePolicy == 1) {
						if (not_dirty != -1) {

							entries.get(index).get(not_dirty).words = result;
							entries.get(index).get(not_dirty).dirty = false;
							entries.get(index).get(not_dirty).valid = true;
							entries.get(index).get(not_dirty).tag = tag;
						} else {
							if (nextLevel instanceof Memory) {
								entries.get(index).get(0).dirty = false;
								entries.get(index).get(0).valid = true;
								ArrayList<String> dirty_block = entries.get(
										index).get(0).words;
								entries.get(index).get(0).words = result;
								((MemoryHierarchy) nextLevel).writeBlock(
										encodeAddress(
												entries.get(index).get(0).tag,
												address), dirty_block);
								entries.get(index).get(0).tag = tag;
								latency += accessTime;
							} else {
								entries.get(index).get(0).words = result;
								entries.get(index).get(0).dirty = true;
								entries.get(index).get(0).valid = true;
								entries.get(index).get(0).tag = tag;
							}
						}
					} else {
						entries.get(index).get(0).words = result;
						entries.get(index).get(0).dirty = false;
						entries.get(index).get(0).valid = true;
						entries.get(index).get(0).tag = tag;
					}
				}

			}
				break;
			case 2: {// full associative
				int not_dirty = -1;
				int found_empty = -1;
				for (int i = 0; i < entries.get(0).size(); i++) {
					if (entries.get(0).get(i).words.size() == 0) {
						found_empty = i;
					} else {
						if (not_dirty == -1)
							not_dirty = entries.get(0).get(i).dirty ? -1 : i;
					}
				}
				if (found_empty != -1) {
					entries.get(0).get(found_empty).words = result;
					entries.get(0).get(found_empty).dirty = false;
					entries.get(0).get(found_empty).tag = tag;
					entries.get(0).get(found_empty).valid = true;
				} else {
					if (not_dirty != -1) {
						entries.get(0).get(not_dirty).words = result;
						entries.get(0).get(not_dirty).dirty = false;
						entries.get(0).get(not_dirty).tag = tag;
						entries.get(0).get(not_dirty).valid = true;
					} else {
						if (nextLevel instanceof Memory) {
							entries.get(0).get(0).dirty = false;
							entries.get(0).get(0).valid = true;
							ArrayList<String> dirty_block = entries.get(0).get(
									0).words;
							entries.get(0).get(0).words = result;
							((MemoryHierarchy) nextLevel).writeBlock(
									encodeAddress(
											entries.get(index).get(0).tag,
											address), dirty_block);
							entries.get(index).get(0).tag = tag;
							latency += accessTime;
						} else {
							entries.get(0).get(0).words = result;
							entries.get(0).get(0).dirty = true;
							entries.get(0).get(0).valid = true;
							entries.get(0).get(0).tag = tag;
						}
					}
				}

			}
				break;

			}

		} else {
			hits++;
		}
		return result;
	}

	public ArrayList<String> write(int address, String word) {
		accesses++;
		latency += accessTime;
		int[] decoded = decodeAddress(address);
		int tag = decoded[0];
		int index = decoded[1];
		int offset = decoded[2];
		ArrayList<String> result = null;
		switch (type) {
		case 0: {

			if (entries.get(index).get(0).tag == tag) {
				if (entries.get(index).get(0).words.size() == 0) {
					for (int i = 0; i < L; i++)
						entries.get(index).get(0).words.add("Word");
				}
				entries.get(index).get(0).words.set(offset, word);
				entries.get(index).get(0).valid = true;
				if (HWritePolicy == 1)
					entries.get(index).get(0).dirty = true;
				entries.get(index).get(0).tag = tag;
				result = entries.get(index).get(0).words;
			}

		}
			break;
		case 1: {

			for (int i = 0; i < entries.get(index).size(); i++) {
				if (tag == entries.get(index).get(i).tag) {
					if (entries.get(index).get(i).words.size() == 0) {
						for (int j = 0; j < L; j++)
							entries.get(index).get(i).words.add("Word");

					}
					entries.get(index).get(i).words.set(offset, word);
					entries.get(index).get(i).valid = true;
					if (HWritePolicy == 1)
						entries.get(index).get(i).dirty = true;
					entries.get(index).get(i).tag = tag;
					result = entries.get(index).get(i).words;

				}
			}
		}
			break;
		case 2: {
			for (int i = 0; i < entries.get(0).size(); i++) {
				if (tag == entries.get(0).get(i).tag) {
					if (entries.get(0).get(i).words.size() == 0) {
						for (int j = 0; j < L; j++)
							entries.get(0).get(i).words.add("Word");
					}
					entries.get(0).get(i).words.set(offset, word);
					entries.get(0).get(i).valid = true;
					if (HWritePolicy == 1)
						entries.get(0).get(i).dirty = true;
					entries.get(0).get(i).tag = tag;
					result = entries.get(0).get(i).words;

				}

			}
		}
			break;

		}

		if (result == null) {
			if (MWritePolicy == 0) {
				((MemoryHierarchy) nextLevel).write(address, word);
				latency -= accessTime;
			} else {
				if (!(MWritePolicy == 2 && nextLevel instanceof Memory)) {
					result = ((MemoryHierarchy) nextLevel).write(address, word);
					latency += accessTime;
				} else {
					result = ((Memory) nextLevel).virtualWrite(address, word);
				}
				
				switch (type) {
				case 0: {// direct-map
					if (MWritePolicy == 2 || HWritePolicy == 1) {
						if (entries.get(index).get(0).dirty) {
							if (nextLevel instanceof Memory) {
								if (MWritePolicy == 2)
									entries.get(index).get(0).dirty = true;
								else
									entries.get(index).get(0).dirty = false;
								entries.get(index).get(0).valid = true;
								ArrayList<String> dirty_block = entries.get(
										index).get(0).words;
								entries.get(index).get(0).words = result;
								((MemoryHierarchy) nextLevel).writeBlock(
										encodeAddress(
												entries.get(index).get(0).tag,
												address), dirty_block);
								entries.get(index).get(0).tag = tag;
								latency += accessTime;
							} else {
								entries.get(index).get(0).words = result;
								if (MWritePolicy == 2)
									entries.get(index).get(0).dirty = true;
								else
									entries.get(index).get(0).dirty = false;
								entries.get(index).get(0).valid = true;
								entries.get(index).get(0).tag = tag;
							}
						} else {
							entries.get(index).get(0).words = result;
							entries.get(index).get(0).tag = tag;
							entries.get(index).get(0).valid = true;
							if (MWritePolicy == 2)
								entries.get(index).get(0).dirty = true;
							else
								entries.get(index).get(0).dirty = false;
						}

					} else {
						if (MWritePolicy == 2)
							entries.get(index).get(0).valid = true;
						else
							entries.get(index).get(0).valid = false;
						entries.get(index).get(0).words = result;
						entries.get(index).get(0).tag = tag;
					}
				}
					break;
				case 1: {// set associative
					int not_dirty = -1;
					int found_empty = -1;
					for (int i = 0; i < entries.get(index).size(); i++) {
						if (entries.get(index).get(i).words.size() == 0
								&& found_empty == -1) {
							found_empty = i;
						} else {
							if (not_dirty == -1)
								not_dirty = entries.get(index).get(i).dirty ? -1: i;
						}
					}
					if (found_empty != -1) {
						entries.get(index).get(found_empty).words = result;
						if (MWritePolicy == 2)
							entries.get(index).get(found_empty).dirty = true;
						else
							entries.get(index).get(found_empty).dirty = false;
						entries.get(index).get(found_empty).valid = true;
						entries.get(index).get(found_empty).tag = tag;
					} else {
						if (MWritePolicy == 2 || HWritePolicy == 1) {
							if (not_dirty != -1) {
								
								entries.get(index).get(not_dirty).words = result;
								if (MWritePolicy == 2)
									entries.get(index).get(not_dirty).dirty = true;
								else
									entries.get(index).get(not_dirty).dirty = false;
								entries.get(index).get(not_dirty).valid = true;
								entries.get(index).get(not_dirty).tag = tag;

							} else {
								if (nextLevel instanceof Memory) {
									entries.get(index).get(0).dirty = false;
									entries.get(index).get(0).valid = true;
									ArrayList<String> dirty_block = entries
											.get(index).get(0).words;
									entries.get(index).get(0).words = result;

									((MemoryHierarchy) nextLevel).writeBlock(
											encodeAddress(entries.get(index)
													.get(0).tag, address),
											dirty_block);
									entries.get(index).get(0).tag = tag;
									latency += accessTime;
								} else {
									entries.get(index).get(0).words = result;
									if (MWritePolicy == 2)
										entries.get(index).get(0).dirty = true;
									else
										entries.get(index).get(0).dirty = false;
									entries.get(index).get(0).valid = true;
									entries.get(index).get(0).tag = tag;
								}
							}
						} else {
							entries.get(index).get(0).words = result;
							if (MWritePolicy == 2)
								entries.get(index).get(0).dirty = true;
							else
								entries.get(index).get(0).dirty = false;
							entries.get(index).get(0).valid = true;
							entries.get(index).get(0).tag = tag;
						}
					}

				}
					break;
				case 2: {// full associative

					int not_dirty = -1;
					int found_empty = -1;
					for (int i = 0; i < entries.get(0).size(); i++) {
						if (entries.get(0).get(i).words.size() == 0&& found_empty == -1) {
							found_empty = i;
						} else {
							if (not_dirty == -1)
								not_dirty = entries.get(0).get(i).dirty ? -1
										: i;
						}
					}
					if (found_empty != -1) {
						entries.get(0).get(found_empty).words = result;
						if (MWritePolicy == 2)
							entries.get(index).get(0).dirty = true;
						else
							entries.get(index).get(0).dirty = false;
						entries.get(0).get(found_empty).valid = true;
						entries.get(0).get(found_empty).tag = tag;
					} else {
						if (not_dirty != -1) {
							entries.get(0).get(not_dirty).words = result;
							if (MWritePolicy == 2)
								entries.get(index).get(0).dirty = true;
							else
								entries.get(index).get(0).dirty = false;
							entries.get(0).get(not_dirty).valid = true;
							entries.get(0).get(not_dirty).tag = tag;
						} else {
							if (nextLevel instanceof Memory) {
								entries.get(0).get(0).dirty = false;
								entries.get(0).get(0).valid = true;
								ArrayList<String> dirty_block = entries.get(0)
										.get(0).words;
								entries.get(0).get(0).words = result;
								((MemoryHierarchy) nextLevel).writeBlock(
										encodeAddress(
												entries.get(index).get(0).tag,
												address), dirty_block);
								entries.get(0).get(0).tag = tag;
								latency += accessTime;
							} else {
								entries.get(0).get(0).words = result;
								if (MWritePolicy == 2)
									entries.get(index).get(0).dirty = true;
								else
									entries.get(index).get(0).dirty = false;
								entries.get(0).get(0).valid = true;
								entries.get(0).get(0).tag = tag;
							}

						}
					}

				}
					break;

				}

			}
		} else {
			hits++;
			if (HWritePolicy == 0) {
				result = ((MemoryHierarchy) nextLevel).write(address, word);
				latency += accessTime;
			} else if (!(nextLevel instanceof Memory)) {
				result = ((MemoryHierarchy) nextLevel).write(address, word);
				latency += accessTime;
			}
		}

		return result;

	}

	// used for writing back when readmiss
	public void writeBlock(int address, ArrayList<String> words) {
		int[] decoded = decodeAddress(address);
		int tag = decoded[0];
		int index = decoded[1];
		int offset = decoded[2];
		switch (type) {
		case 0: {
			if (entries.get(index).get(0).tag == tag) {
				entries.get(index).get(0).words = words;
				entries.get(index).get(0).valid = true;
				entries.get(index).get(0).dirty = true;
			}
		}
			break;
		case 1: {
			for (int i = 0; i < entries.get(index).size(); i++) {
				if (tag == entries.get(index).get(i).tag) {
					entries.get(index).get(i).words = words;
					entries.get(index).get(i).valid = true;
					entries.get(index).get(i).dirty = false;
				}
			}
		}
			break;
		case 2: {
			for (int i = 0; i < entries.get(0).size(); i++) {
				if (tag == entries.get(0).get(i).tag) {
					entries.get(0).get(i).words = words;
					entries.get(0).get(i).valid = true;
					entries.get(0).get(i).dirty = false;
				}

			}
		}
			break;

		}
		((MemoryHierarchy) nextLevel).writeBlock(address, words);
		latency += accessTime;
	}

	public double getHitRate() {
            if (accesses == 0) return 0.0;
            return hits*1.0 / accesses*1.0;
	}

	public CacheOutputPack getLoadLatency(int address) {
		ArrayList<String> block = read(address);
		int[] decoded = decodeAddress(address);
		int temp = latency;
		latency = 0;
		CacheOutputPack out = new CacheOutputPack(temp, block.get(decoded[2]));
		return out;
	}

	public CacheOutputPack getStoreLatency(int address, String word) {
		write(address, word);
		int temp = latency;
		latency = 0;
		CacheOutputPack out = new CacheOutputPack(temp, word);
		return out;
	}
	
	public class CacheOutputPack {
		public int latency;
		public String word;

		public CacheOutputPack(int _latency, String _word) {
			this.latency = _latency;
			this.word = _word;
		}
	}

	// cache entry class
	public class CacheEntry {
		private boolean valid; // valid bit
		private boolean dirty; // dirty bit
		private int tag; // tag
		private int L;
		private ArrayList<String> words;

		public CacheEntry(int L) {
			this.valid = false;
			this.dirty = false;
			this.tag = -1;
			this.L = L;
			this.words = new ArrayList<String>(L);
		}

		public boolean isValid() {
			return valid;
		}

		public void setValid(boolean valid) {
			this.valid = valid;
		}

		public boolean isDirty() {
			return dirty;
		}

		public void setDirty(boolean dirty) {
			this.dirty = dirty;
		}

		public int getTag() {
			return tag;
		}

		public void setTag(int tag) {
			this.tag = tag;
		}

		public ArrayList<String> getWords() {
			return words;
		}

		public void setWords(ArrayList<String> words) {
			this.words = words;
		}

		public String toString() {
			return words.toString();
		}
	}

	public static void main(String[] args) {
		Cache c = new Cache(8, 2, 4, 0, 1, 1);
		Cache c2 = new Cache(8, 2, 2, 0, 1, 1);
		Cache c3 = new Cache(8, 2, 1, 0, 1, 1);
		Memory m = new Memory(32, 2, 1);
		c.setNextLevel(c2);
		c2.setNextLevel(c3);
		c3.setNextLevel(m);
		c.write(14, "mina");
		System.out.println(c.entries);
		System.out.println(c2.entries);
		System.out.println(c3.entries);
		System.out.println(m.memory);
		System.out.println("Latency" + latency);
		latency = 0;
		c.write(15, "fadi");
		System.out.println(c.entries);
		System.out.println(c2.entries);
		System.out.println(c3.entries);
		System.out.println(m.memory);
		System.out.println("Latency" + latency);
		latency = 0;
		c.write(6, "Jolly");
		System.out.println(c.entries);
		System.out.println(c2.entries);
		System.out.println(c3.entries);
		System.out.println(m.memory);
		System.out.println("Latency" + latency);
		latency = 0;
		c.write(7, "Jolly");
		System.out.println(c.entries);
		System.out.println(c2.entries);
		System.out.println(c3.entries);
		System.out.println(m.memory);
		System.out.println("Latency" + latency);
		latency = 0;
		c.write(30, "minaR");
		System.out.println(c.entries);
		System.out.println(c2.entries);
		System.out.println(c3.entries);
		System.out.println(m.memory);
		System.out.println("Latency" + latency);
		latency = 0;
		c.write(31, "fadiR");
		System.out.println(c.entries);
		System.out.println(c2.entries);
		System.out.println(c3.entries);
		System.out.println(m.memory);
		System.out.println("Latency" + latency);
		latency = 0;
		System.out.println(c.read(30));
		System.out.println(c.entries);
		System.out.println(c2.entries);
		System.out.println(c3.entries);
		System.out.println(m.memory);
		System.out.println("Latency" + latency);
		latency = 0;
		System.out.println(c.read(31));
		System.out.println(c.entries);
		System.out.println(c2.entries);
		System.out.println(c3.entries);
		System.out.println(m.memory);
		System.out.println("Latency" + latency);
		latency = 0;
		c.write(30, "christineR");
		System.out.println(c.entries);
		System.out.println(c2.entries);
		System.out.println(c3.entries);
		System.out.println(m.memory);
		System.out.println("Latency" + latency);
		latency = 0;
		System.out.println(c.read(14));
		System.out.println(c.entries);
		System.out.println(c2.entries);
		System.out.println(c3.entries);
		System.out.println(m.memory);
		System.out.println("Latency" + latency);
		latency = 0;
		System.out.println(c.read(6));
		System.out.println(c.entries);
		System.out.println(c2.entries);
		System.out.println(c3.entries);
		System.out.println(m.memory);
		System.out.println("Latency" + latency);
		latency = 0;
		System.out.println(c.getHitRate());
	}
}
